package oj_hihocode;

import java.util.Scanner;

/**
 * Created by zhangyi on 2017/7/13.
 */

/**
 * Prim
 */
public class T1097 {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int Ans = 0;
        int N = in.nextInt();
        int[][] matrix = new int[N + 1][N + 1];

        //优先队列
        City[] queue = new City[N + 1];
        int size = N;

        int[] kueue = new int[N + 1];//每个城市在队列中的位置，不存在则为0

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                matrix[i][j] = in.nextInt();
            }
            queue[i] = new City(i, 10000);//由题目给出的范围得出
        }

        //初始化堆内元素
        for (int i = 1; i <= N; i++) {
            queue[i].setDistance(matrix[1][i]);
            kueue[i] = i;
        }
        queue[1] = queue[size];

        kueue[size] = 1;
        kueue[1] = 0;
        size--;

        //构造堆
        for (int i = size / 2; i >= 1; i--) {
            int pos = i;
            while (pos <= size / 2) {
                int minChild;// 最小子元素的位置
                if (pos * 2 + 1 > size) {
                    minChild = pos * 2;
                } else {
                    if (queue[pos * 2].getDistance() < queue[pos * 2 + 1].getDistance()) {
                        minChild = pos * 2;
                    } else {
                        minChild = pos * 2 + 1;
                    }
                }
                if (queue[pos].getDistance() > queue[minChild].getDistance()) {
                    //queue
                    City tmp = queue[pos];
                    queue[pos] = queue[minChild];
                    queue[minChild] = tmp;

                    //kueue
                    kueue[queue[pos].getId()] = pos;
                    kueue[queue[minChild].getId()] = minChild;

                    pos = minChild;
                } else {
                    break;
                }
            }
        }


        //不断删除最小的(下沉)，并更新堆内的值(上浮)
        while (size > 0) {
            Ans += queue[1].getDistance();

            City rm = queue[1];
            queue[1] = queue[size];
            //System.out.println(rm.getDistance());

            kueue[rm.getId()] = 0;
            kueue[queue[1].getId()] = 1;
            size--;

            int pos = 1;
            while (pos <= size / 2) {
                int minChild;// 最小子元素的位置
                if (pos * 2 + 1 > size) {
                    minChild = pos * 2;
                } else {
                    if (queue[pos * 2].getDistance() < queue[pos * 2 + 1].getDistance()) {
                        minChild = pos * 2;
                    } else {
                        minChild = pos * 2 + 1;
                    }
                }
                if (queue[pos].getDistance() > queue[minChild].getDistance()) {
                    //queue
                    City tmp = queue[pos];
                    queue[pos] = queue[minChild];
                    queue[minChild] = tmp;

                    //kueue
                    kueue[queue[pos].getId()] = pos;
                    kueue[queue[minChild].getId()] = minChild;

                    pos = minChild;
                } else {
                    break;
                }
            }


            //更新
            for (int i = 1; i <= N; i++) {
                //i在队列中
                if (kueue[i] != 0 && queue[kueue[i]].getDistance() > matrix[rm.getId()][i]) {
                    queue[kueue[i]].setDistance(matrix[rm.getId()][i]);
                    int start = kueue[i];
                    while (start > 1 && queue[start].getDistance() < queue[start / 2].getDistance()) {
                        //queue
                        City tmp = queue[start];
                        queue[start] = queue[start / 2];
                        queue[start / 2] = tmp;

                        //kueue
                        kueue[queue[start].getId()] = start;
                        kueue[queue[start / 2].getId()] = start / 2;

                        start = start / 2;
                    }
                }
            }


        }

        System.out.println(Ans);


    }


    static class City {
        int id;
        int distance;

        City(int id, int distance) {
            this.id = id;
            this.distance = distance;
        }

        public int getId() {
            return id;
        }

        public void setId(int id) {
            this.id = id;
        }

        public int getDistance() {
            return distance;
        }

        public void setDistance(int distance) {
            this.distance = distance;
        }
    }


}
